package com.example.leetcode.BFS;

import java.util.*;

/**
 * 建立各个节点的出度表
 * @ClassName Solution_12_310
 * @Description
 *
 * 思路：https://leetcode-cn.com/problems/minimum-height-trees/solution/c-you-wai-zhi-nei-de-ceng-xu-bian-li-by-dnu8g/
 * 代码：https://leetcode-cn.com/problems/minimum-height-trees/solution/zui-rong-yi-li-jie-de-bfsfen-xi-jian-dan-zhu-shi-x/
 *
 * 思路：由外至内层序遍历，找到最小高度树，就像层序遍历，从最外层一层一层往里数，当剩下的元素均在同一层时，这些元素就是最小层元素
 *      拥有相同度数的元素作为同一层。
 *      将度数为一的那一层元素去掉，与之相连的倒数第二层的节点，度数会在去掉倒数第一层的节点过程中，度数变一，这样倒数第二层元素
 *      就变成了度数为一的一层元素，继续。。。
 *
 * 输入：n = 4, edges = [[1,0],[1,2],[1,3]]
 * 输出：[1]
 * 解释：如图所示，当根是标签为 1 的节点时，树的高度是 1 ，这是唯一的最小高度树。
 *
 *
 * @Author liuzhihui
 * @Date 19/6/2021 上午 11:38
 * @Version 1.0
 **/
public class Solution_12_310 {
    public static void main(String[] args) {
        int[][] edges = new int[][]{{1,0},{1,2},{1,3}};
        int n = 4;
        List<Integer> findMinHeightTrees2 = findMinHeightTrees2(n, edges);
        System.out.println();
    }
    public static List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> res = new ArrayList<>();

        // 如果只有一个节点，那么他就是最小高度树
        if (n == 1) {
            res.add(0);
            return res;
        }

        //  1、建立各个节点的出度表
        // 下标表示节点，值表示节点的出度
        int[] degree = new int[n];

        // 2、建立图关系，在每个节点的list中存储相连节点
        // 下标表示每个节点，里面的元素集合，表示该节点与哪些节点相连
        List<List<Integer>> map = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            map.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            // 节点edge[0]的出度加一
            degree[edge[0]]++;
            // 节点edge[1]的出度加一
            degree[edge[1]]++;
            // 与节点edge[0]相连的边，添加进集合中
            map.get(edge[0]).add(edge[1]);
            // 与节点edge[1]相连的边，添加进集合中
            map.get(edge[1]).add(edge[0]);
        }

        // 3、建立队列
        Queue<Integer> queue = new LinkedList<>();
        // 4、把所有出度为1的节点，也就是叶子节点入队，最外层节点入队列
        for (int i = 0; i < n; i++) {
            if (degree[i] == 1) {
                queue.offer(i);
            }
        }
        // 5、遍历当前层的元素
        while (!queue.isEmpty()) {
            // 注意：每次循环都要清除，存下的上一层节点，以便存当前这一层的节点
            res.clear();
            // 这是每一层的节点的数量
            int size = queue.size();
            // 遍历当层节点
            for (int i = 0; i < size; i++) {
                // 取出当前节点的元素
                int cur = queue.poll();
                // 添加到结果集中
                res.add(cur);
                // 获取当前节点的邻边
                List<Integer> neighbors = map.get(cur);
                // 遍历邻边
                for (int neighbor : neighbors) {
                    // 邻边的度数减一；如果当前层是，最后一层，经过--,就直接return了
                    degree[neighbor]--;
                    // 当邻边的度数等于1时，邻边作为下一层的元素，加入队列中
                    if (degree[neighbor] == 1) {
                        // 如果是叶子节点我们就入队
                        queue.offer(neighbor);
                    }
                }
            }
        }
        return res;
    }
    // 使用List<List<Integer>> map = new ArrayList<>(); 效率比使用Map<Integer, List<Integer>> map = new LinkedHashMap<>(); 高
    public static List<Integer> findMinHeightTrees2(int n, int[][] edges){
        List<Integer> res = new ArrayList<>();

        if (edges.length == 1){
            res.add(0);
            return res;
        }

        // 1、记录每条边的出度
        int[] degrees = new int[n];

        // 2、记录每条边和哪些边相邻
        Map<Integer, List<Integer>> map = new LinkedHashMap<>();
        for (int[] edge : edges) {
            // 节点edge[0]的出度加一
            degrees[edge[0]]++;
            // 节点edge[1]的出度加一
            degrees[edge[1]]++;

            List<Integer> list = map.get(edge[0]);
            list = list == null ? new ArrayList<>() : list;
            list.add(edge[1]);
            // 当前边edge[0]，与哪些边list相连
            map.put(edge[0],list);

            list = map.get(edge[1]);
            list = list == null ? new ArrayList<>() : list;
            list.add(edge[0]);
            // 当前边edge[1]，与哪些边list相连
            map.put(edge[1],list);
        }

        // 3、创建一个队列,用于存储一层的数据
        Deque<Integer> deque = new LinkedList<>();

        // 4、将出度为一的一层，也就是最外层，放到队列中
        for (int i = 0; i < degrees.length; i++) {
            if (degrees[i] == 1){
                deque.add(i);
            }
        }

        // 5、遍历当前层元素
        while(!deque.isEmpty()){
            // 将上一层的元素清除
            res.clear();
            // 获取当前层元素个数
            int size = deque.size();
            // 遍历当前层元素
            for (int i = 0; i < size; i++) {
                // 取出一个元素
                Integer pop = deque.pop();
                // 将当前元素加到结果集合中
                res.add(pop);

                // 获取当前元素的邻接元素
                List<Integer> list = map.get(pop);
                // 遍历邻接元素
                for (Integer integer : list) {
                    // 邻接元素度数减一
                    degrees[integer]--;
                    // 如果邻接元素的度数为1，那么它将放到队列里，作为下一层的元素
                    if (degrees[integer] == 1){
                        deque.add(integer);
                    }
                }
            }
        }
        return res;
    }


}
